package list

func solveSudoku(board [][]byte) {
	// write code here
	m, n := len(board), len(board[0])
	var backtrack func(x, y int) bool
	backtrack = func(x, y int) bool {
		if y == n {
			return backtrack(x+1, 0)
		}

		if x == m {
			return true
		}

		if board[x][y] != '.' {
			return backtrack(x, y+1)
		}

		for c := byte('1'); c <= byte('9'); c++ {
			if !isValid(board, x, y, c) {
				continue
			}

			board[x][y] = c

			if backtrack(x, y+1) {
				return true
			}

			board[x][y] = '.'
		}

		return false
	}

	backtrack(0, 0)
}

func isValid(board [][]byte, x, y int, target byte) bool {
	for i := 0; i < 9; i++ {
		if board[i][y] == target {
			return false
		}

		if board[x][i] == target {
			return false
		}

		xx, yy := (x/3)*3+i/3, (y/3)*3+i%3
		if board[xx][yy] == target {
			return false
		}
	}
	return true
}
